#include "algorithm.h"

// int array[] = {2, 8, 4, 1, 9, 3, 7, 6, 5, 0};
void insert_sort(int *array, int len)
{

    int temp, j;
    /**
     * non-decreasing
     * **/
    // for(int i = 1; i < len; i++){
    //     if(array[i-1] > array[i]){
    //         temp = array[i];

    //         for(j = i-1; j >= 0 && array[j] > temp; j --)
    //             array[j+1] = array[j];

    //         array[j+1] = temp;
    //     }
    // }

    /**
     * decreasing
     * **/
    for (int i = 1; i < len - 1; i++)
    {
        if (array[i - 1] < array[i])
        {
            temp = array[i];

            for (j = i - 1; j >= 0 && array[j] < temp; j--)
                array[j + 1] = array[j];

            array[j + 1] = temp;
        }
    }
}

static int quick_sort_partition(int *array, int low, int high)
{
    int pivot = array[low];
    while (low < high)
    {
        while (low < high && array[high] >= pivot)
            --high;
        array[low] = array[high];

        while (low < high && array[low] <= pivot)
            ++low;
        array[high] = array[low];
    }

    array[low] = pivot;
    return low;
}

static void quick_sort_inner(int *array, int low, int high)
{
    if (low < high)
    {
        int pivot = quick_sort_partition(array, low, high);
        quick_sort_inner(array, low, pivot - 1);
        quick_sort_inner(array, pivot + 1, high);
    }
}

void quick_sort(int *array, int len)
{
    quick_sort_inner(array, 0, len - 1);
}

void shell_sort(int *array, int len)
{
    int j;
    int temp;

    for (int gap = len / 2; gap > 0; gap = gap / 2)
    {

        for (int i = gap; i < len; i++)
        {
            if (array[i - gap] > array[i])
            {
                temp = array[i];

                for (j = i; j >= gap && array[j - gap] > temp; j -= gap)
                    array[j] = array[j - gap];

                array[j] = temp;
            }
        }
    }
}

// let array = {2, 3, 9, 1, 12, 23} // [0,5](6)
// len = array.size()

void bubble_sort(int *array, int len)
{
    int temp;

    for (int i = 0; i < len - 1; i++)
    {
        for (int j = 0; j < len - 1; j++)
        {
            if (array[j] < array[j + 1])
            {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}